package io.adrainty.algorithm.mars;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 创意标题匹配问题
 * @link <a href="https://www.marscode.cn/practice/364l85wv6oo6lq?problem_id=7414004855075520556">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/11/22 上午9:44
 */

@SuppressWarnings("unused")
public class Solution007 {

    private Solution007() {}

    public static String solution(int n, String template_, String[] titles) {
        // Please write your code here
        StringBuilder template = new StringBuilder();
        for (int i = 0; i < template_.length(); i++) {
            if (template_.charAt(i) == '}') {
                int j = template.length();
                while (template.charAt(j - 1) != '{') j--;
                template.setLength(j);
            } else {
                template.append(template_.charAt(i));
            }
        }
        System.out.println(template);
        // 替换后 '{' 为通配符
        List<String> result = new ArrayList<>();
        for (String title : titles) {
            result.add(isMatch(template, title));
        }
        return result.stream().map(Object::toString).collect(Collectors.joining(","));
    }

    /**
     * 判断两个字符串是否匹配
     *
     * @param template 模板
     * @param title    标题
     * @return 是否匹配
     */
    private static String isMatch(CharSequence template, String title) {
        int m = template.length();
        int n = title.length();
        // dp[i][j] 表示 template 前 i 个字符 和 title 前 j 个字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 默认空串和空标题匹配
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            if (template.charAt(i - 1) != '{') {
                // 固定字符要求
                // 1. 左上角为True 即template的前i个字符和title的前j个字符匹配，
                // 2. 当前两个字符相等
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = dp[i - 1][j - 1] && template.charAt(i - 1) == title.charAt(j - 1);
                }
            } else {
                // 通配符要求
                // 左上角为True 即template的前i-1个字符和title的前j个字符匹配，即可为true
                // notice: 有可能没有字符 即空串也是匹配的
                for (int j = 0; j <= n; j++) {
                    for (int k = 0; k <= j; k++) {
                        dp[i][j] = dp[i][j] || dp[i - 1][k];
                    }
                }
            }
        }
        return dp[template.length()][title.length()]? "True": "False";
    }

}
